﻿

‍
typedef struct node
{
    ElemType element;
    struct node* link;
}Node;

‍

‍
typedef struct headerlist
{
    Node* head;
    int n;
}HeaderList;

void MergeList1(HeaderList* La, HeaderList* Lb, HeaderList* Lc) {
    // 合并链表La和Lb，合并后的新表使用头指针Lc指向 
    Node* pa, * pb, * pc, * q;
    pa = La->head->link;
    pb = Lb->head->link;
    pc = Lc->head;

    while (pa && pb) {
        if (pa->element <= pb->element) {
            pc->link = pa;
            pc = pa;
            pa = pa->link;
            La->n--;
        }
        else if (pa->element > pb->element) {
            pc->link = pb;
            pc = pb;
            pb = pb->link;
            Lb->n--;
        }
        else {
            pc->link = pa;
            pc = pa;
            pa = pa->link;
            q = pb;
            free(q);
            pb = q;
        }
        Lc->n++;
    }

    pc->link = pa ? pa : pb; // 插入剩余段 
    Lc->n += pa ? La->n : Lb->n;
}